package sort

import (
	"container/heap"
	"fmt"
)

func bubbleSort202206(nums []int) {
	var n = len(nums)
	for i := 0; i < n; i++ {
		for j := 0; j < n-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

func insert202206(nums []int) {
	var n = len(nums)
	for i := 1; i < n; i++ {
		var val = nums[i]
		var targetIdx = i - 1
		for targetIdx >= 0 && nums[targetIdx] > val {
			nums[targetIdx+1] = nums[targetIdx]
			targetIdx--
		}
		targetIdx++
		nums[targetIdx] = val
	}
}

func select202206(nums []int) {
	var n = len(nums)
	for i := 0; i < n-1; i++ {
		var minIdx = i
		for j := i + 1; j < n; j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		if minIdx != i {
			nums[i], nums[minIdx] = nums[minIdx], nums[i]
		}
	}
}

func quickSort202206(nums []int) {
	quickSort202206Dfs(nums, 0, len(nums)-1)
}

func quickSort202206Dfs(nums []int, low, high int) {
	if low < high {
		var (
			left   = low
			right  = high
			midVal = nums[low]
		)

		for left < right {
			for left < right && nums[right] > midVal {
				right--
			}
			if left < right {
				nums[left] = nums[right]
				left++
			}

			for left < right && nums[left] < midVal {
				left++
			}
			if left < right {
				nums[right] = nums[left]
				right--
			}
		}
		nums[left] = midVal
		quickSort202206Dfs(nums, low, left-1)
		quickSort202206Dfs(nums, left+1, high)
	}
}

/**
 * @Description: 归并排序
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/7 7:35
 **/
func mergeSort20220607(nums []int) {
	size := len(nums)
	if size < 2 {
		return
	}
	var midIdx = size / 2
	var left = make([]int, midIdx)
	copy(left, nums[0:midIdx])
	var right = make([]int, size-midIdx)
	copy(right, nums[midIdx:])
	mergeSort20220607(left)
	mergeSort20220607(right)
	merge20220607(left, right, nums)
}
func merge20220607(nums1, nums2, nums3 []int) {
	n1 := len(nums1)
	n2 := len(nums2)
	var idx1 = 0
	var idx2 = 0
	var idx3 = 0
	for idx1 < n1 || idx2 < n2 {
		if idx1 < n1 && idx2 < n2 {
			if nums1[idx1] < nums2[idx2] {
				nums3[idx3] = nums1[idx1]
				idx1++
			} else {
				nums3[idx3] = nums2[idx2]
				idx2++
			}
			idx3++
			continue
		}
		if idx1 < n1 {
			nums3[idx3] = nums1[idx1]
			idx1++
			idx3++
			continue
		}
		if idx2 < n2 {
			nums3[idx3] = nums2[idx2]
			idx2++
			idx3++
			continue
		}
	}
}

type array []int

func (a *array) Push(x any) {
	*a = append(*a, x.(int))
}
func (a *array) Pop() any {
	var n = len(*a)
	var x = (*a)[n-1]
	*a = (*a)[0 : n-1]
	return x
}
func (a *array) Len() int {
	return len(*a)
}
func (a *array) Less(i, j int) bool {
	return (*a)[i] < (*a)[j]
}
func (a *array) Swap(i, j int) {
	(*a)[i], (*a)[j] = (*a)[j], (*a)[i]
}

func TopK(arr []int, k int) {
	var a = &array{}
	heap.Init(a)
	for i := 0; i < len(arr); i++ {
		heap.Push(a, arr[i])
		if len(*a) > k {
			heap.Pop(a)
		}
	}

	for i := 0; i < len(*a); i++ {
		fmt.Println("top k ：", (*a)[i])
	}
}
